﻿using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace SolverTemplateLib.BackTracker
{
    /// <summary>
    /// Solve the Queens problem using my Backtracker class.
    /// http://en.wikipedia.org/wiki/Eight_queens_puzzle
    /// Of course generalized to N queens.
    /// 
    /// </summary>
    [Serializable]
    public class DerangementBackTracker : Backtracker
    {
        #region Problem specific
        public static int N = 8; // Number of queens required
        public static int S = 0; // Number of solutions
        public DerangementBackTracker(int numberOfQueens)
        {
            n = 0;
            N = numberOfQueens;
            q = new int[N];
            S = 0;
        }

        private int n;
        private int[] q;

        public int[] Q
        {
            get { return q; }
        }

        #endregion

        #region Backtracker interface to implement
        /// <summary>
        /// 
        /// </summary>
        /// <returns>
        /// True if the current candidate is a solution
        /// </returns>
        public override bool IsSolution()
        {
            return n == N;
        }

        public override void ProcessSolution()
        {
            Interlocked.Increment(ref S);
        }

        public override List<Backtracker> Candidates()
        {
            var result = new List<Backtracker>();

            // Parallelism not recommended here, List<T> is not thread safe
            for (int i = 0; i < N; i++)
//                Parallel.For(0, N, i =>
                    {
                        if (i != n)
                        {
                            bool valid = true;

                            for (int a = 0; (a < n) && valid; a++)
                                valid &= (q[a] != i);

                            if (valid)
                            {
                                var q1 = new int[N];
                                Array.Copy(q, q1, n);
                                q1[n] = i;

                                result.Add(new DerangementBackTracker(N)
                                    {
                                        q = q1,
                                        n = n + 1,
                                    });
                            }
                        }
                    }
//            )
            ;

            return result;
        }

        public override void ProcessCandidate()
        {
        }

        /// <summary>
        /// Check for cancellation
        /// </summary>
        /// <returns>
        /// True if backtracking is cancelled somewhere
        /// </returns>
        public override bool IsCancelled()
        {
            return false;
        }
        #endregion
    }
}
